Section: New Results

A Global Constraint for Multi-Agent Localization (constraints and application)

Participants : Gilles Chabert, Sophie Demassey.

This work has been initiated in the context of the Angels research project, in which G. Chabert has been involved during two years. The idea was to provide a new method for inter-localizing a group of autonomous underwater robots, traditional Kalman-based methods being inadequate in this context due to the highly nonlinear models derived from the sensing technology (electric fish robots).

We proposed, through a rough discretization of the signals, to consider the problem as a whole and under a combinatorial form. The level of the signal is basically associated to a cardinality of surrounding objects. This led to a global constraint, namely a conjunction of among constraint with interval value domains and in multiple dimension (objects are variables with several components).

Conjunction of among constraints had been already studied but not in the case of interval value domains. We therefore conducted a theoretical study and proved that the problem was tractable in the one-dimensional case, but not in higher dimension. We have also investigated different decompositions and filtering algorithms. This work is submitted to CPAIOR 2012 . An INRIA research report has also been issued in June 2011, where the robotics aspects are described.